/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/convert-sorted-list-to-binary-search-tree
   @Language: C++
   @Datetime: 19-07-16 19:17
   */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
	TreeNode *preorder(ListNode *head, int len){
		if(head==NULL || len==0) return NULL;
		ListNode *mid=head;
		for(int i=len>>1; i--; mid=mid->next);
		TreeNode *root=new TreeNode(mid->val);
		root->left=preorder(head,len>>1);
		root->right=preorder(mid->next,len-(len>>1)-1);
		return root;
	}
public:
	TreeNode* sortedListToBST(ListNode* head) {
		int len=0;
		for(ListNode *i=head; i; ++len, i=i->next);
		return preorder(head, len);
	}
};
